package doublepointer;

/**
 * @Classname : MinimumWindowSubstring
 * @Description : <a href="https://leetcode.cn/problems/minimum-window-substring/">76. 最小覆盖子串</a>
 * @Author : chentianyu
 * @Date 2023/2/23 23:52
 */


public class MinimumWindowSubstring {
    public String minWindow(String s, String t) {
        boolean[] flag = new boolean[128];
        int[] chars = new int[128];
        for(int i=0; i<t.length(); i++) {
            flag[t.charAt(i)] = true;
            chars[t.charAt(i)]++;
        }
        int l = 0, minL = 0, minSize = s.length() + 1, cnt = 0;
        for (int r=0; r<s.length(); r++) {
            if (flag[s.charAt(r)]) {
                if (--chars[s.charAt(r)] >= 0) cnt++;
            }
            while (cnt == t.length()) {
                if (r - l + 1 < minSize) {
                    minL = l;
                    minSize = r - l + 1;
                }
                if (flag[s.charAt(l)] && ++chars[s.charAt(l)] > 0) cnt--;
                l++;
            }
        }
        return minSize > s.length() ? "" : s.substring(minL, minL+minSize);
    }

}
